// DFSThreading.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

struct TreeNode
{
    int value;
    TreeNode *left, *right;
};

// In-order threading a given Binary tree. Making all right child pointers that would normally be null point
// to the in-order successor of the node, and all left child pointers that would normally be null point
// to the in-order predecessor of the node.

// Algorithm: In-order traverse the tree. Always keep 'Prev' and 'Current' pointers to the last visited and current node respectively.
//            Then compare Prev and Current:
//              if Current->left is null, Current->left = Prev
//              if Prev->right is null, Prev->right = Current
// Iteration
void ThreadingBT_InOrder(TreeNode *root)
{
    if(!root) return;
    stack<TreeNode *> s;
    s.push(root);
    TreeNode *prev=NULL;
    int last=0; // 0:up, 1:left, 2:right
    while(!s.empty())
    {
        TreeNode *p=s.top();
        if(last==0)
        {
            if(p->left)
            {
                last=0;
                s.push(p->left);
            }
            else
            {
                last=1;
            }
        }
        else if(last==1)
        {
            // Threading
            if(!p->left)
            {
                p->left=prev;
            }
            if(prev&&!prev->right)
            {
                prev->right=p;
            }
            prev=p;

            if(p->right)
            {
                last=0;
                s.push(p->right);
            }
            else
            {
                last=2;
            }
        }
        else if(last==2)
        {
            s.pop();
            if(!s.empty()&&s.top()->left==p)
            {
                last=1;
            }
            else
            {
                last=2;
            }
        }
        else
            throw;
    }
}

// Recursion
// Analysis:
//  Time Complexity: O(n)
//  Space Complexity: O(H)
void ThreadingBT_InOrder_R(TreeNode *node, TreeNode *&prev) // by ref
{
    if(!node) return;
    ThreadingBT_InOrder_R(node->left,prev);

    if(!node->left)
    {
        node->left=prev;
    }
    if(prev&&!prev->right)
    {
        prev->right=node;
    }
    prev=node;

    ThreadingBT_InOrder_R(node->right,prev);
}

void ThreadingBT_InOrder_R(TreeNode *root)
{
    if(!root) return;
    TreeNode *prev=NULL;
    ThreadingBT_InOrder_R(root,prev);
}

//  Test Case:
//                  100
//             ______|_____
//            |            |
//            50          150
//         ___|___      ___|___
//        |       |    |       |
//        25     75   125     175
//      __|   _|
//     |     |
//     65   110
//     |__
//     |
//    115


// Pre-Order threading a given binary tree
void ThreadingBT_PreOrder(TreeNode *node, TreeNode *&prev) // by ref
{
    if(!node) return;

    if(!node->left)
    {
        node->left=prev;
    }
    if(prev&&!prev->right)
    {
        prev->right=node;
    }
    prev=node;

    ThreadingBT_PreOrder(node->left,prev);
    ThreadingBT_PreOrder(node->right,prev);
}

// Post-Order threading a given binary tree
void ThreadingBT_PostOrder(TreeNode *node, TreeNode *&prev) // by ref
{
    if(!node) return;

    ThreadingBT_PostOrder(node->left,prev);
    ThreadingBT_PostOrder(node->right,prev);

    if(!node->left)
    {
        node->left=prev;
    }
    if(prev&&!prev->right)
    {
        prev->right=node;
    }
    prev=node;
}

int _tmain(int argc, _TCHAR* argv[])
{
    return getchar();
}